public class ProductExceptSelf {
    // leetcode 除自身以外数组的乘积
    // https://leetcode.cn/problems/product-of-array-except-self/description/?envType=study-plan-v2&envId=top-100-liked
    public int[] productExceptSelf(int[] nums) {
        int n  = nums.length;
        int[] leftProduct = new int[n];
        int[] rightProduct = new int[n];
        int product = 1;
        for (int i = 0; i < n; i++) {
            leftProduct[i] = product;
            product *= nums[i];
        }
        product = 1;
        for (int i = n-1; i>= 0; i--) {
            rightProduct[i] = product;
            product *= nums[i];
        }
        int[] ret = new int[n];
        for (int i = 0; i < n; i++) {
            ret[i] = leftProduct[i] * rightProduct[i];
        }
        return ret;
    }
}
